﻿#pragma once
#include<vector>
#include<map>
using namespace std;
template<class T>
class KeyUnionFind
{
public:
	bool Set(const T& key)
	{
		if (_key.find(key)==_key.end())
			return false;

		_key.insert(key, _parents.size());
		_parents.push_back(-1);
	}

	int FindRoot(int child)
	{
		int root = child;
		while (_parents[root] >= 0)
		{
			root = _parents[root];
		}

		return root;
	}

	bool Union(const T& key1, const T& key2)
	{
		auto ikey1 = _key.find(key1);
		auto ikey2 = _key.find(key2);
		if (ikey1 == _key.end() || ikey2 == _key.end())
			return false;

		int root1 = FindRoot(ikey1->second);
		int root2 = FindRoot(ikey2->second);

		if (root1 == root2)
			return false;

		_parents[root1] += _parents[root2];
		_parents[root2] = root1;

		return true;
	}

	size_t UnionNum() const
	{
		size_t ret = 0;
		for (auto e : _parents)
		{
			if (e < 0)
				ret++;
		}

		return ret;
	}
private:
	map<T, int> _key;
	vector<int> _parents;
};

class UnionFind
{
public:
	UnionFind(size_t n)
		:_parents(n,-1)
	{}

	int FindRoot(int child)
	{
		while (_parents[child]>=0)
		{
			child = _parents[child];
		}
		
		return child;
	}

	bool Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);

		if (root1 == root2)
			return false;

		_parents[root1] += _parents[root2];
		_parents[root2] = root1;

		return true;
	}

	size_t UnionNum() const
	{
		size_t ret = 0;
		for (auto e : _parents)
		{
			if (e < 0)
				ret++;
		}

		return ret;
	}
private:
	vector<int> _parents;
};

